package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class SuperEggDropByDpFunc {

    private Map<String,Integer> memo;

    private int dp(int k,int n){
        //写出base-case
        if(k==1){
            return n;
        }
        if(n==0 || n==1){
            return 0;
        }
        String key = k+","+n;
        Integer num = memo.get(key);
        if(num!=null){
            return num;
        }
        int res = Integer.MAX_VALUE;
        for(int i = 1;i<=n;i++){
            res = Math.min(res,Math.max(dp(k,n-i),dp(k-1,i-1))+1);//+1是因为用了一次扔鸡蛋的次数
        }
        memo.put(key,res);
        return res;
    }

    public int superEggDrop(int K, int N) {
        memo = new HashMap<>();
        return dp(K,N);
    }
    @Test
    public void test(){
        System.out.println(superEggDrop(1,2));
        System.out.println(superEggDrop(2,6));
        System.out.println(superEggDrop(3,14));
    }

}
